package chapter02;

public class Search81 {
    /**
     * 二分法
     * 数组经过旋转 二分后一定能分成两部分 一部分一定有序 另一部分可能有序也可能一部分有序
     * 本题会出现重复元素 想办法去除重复元素
     * 一分为二 经过旋转 前一半中重复元素可能会分散在两端 减少左端重复元素
     * while(L<=M&&nums[L]==nums[M])
     *  L++
     * 如果 L>M 无需再判断左右端是否有序只需判断 [L,R]
     * 否则 选取前半部分判断
     *    1）前半部分有序 nums[left]<=nums[mid] 小于等于是为了涵盖只剩下两个元素时判断
     *       a.nums[left]<=target&&target<nums[mid]  target位于[left,mid-1]
     *       b.否则target位于[mid+1,right]
     *    2)否则前半部分无序
     *       a.nums[mid]<target&&target<=nums[right]  巧用后半部分有序判断 target位于[mid+1,right]
     *       b.否则 target位于[left,mid-1]
     */
    public boolean search(int[] nums, int target) {
        int L=0;
        int R=nums.length-1;
        while (L<=R){
            int M=(L+R)/2;
            if(nums[M]==target){
                return true;
            }
            while (L<=M&&nums[L]==nums[M]){
                L++;
            }
            if(L>M){
                continue;
            }
            if(nums[L]<=nums[M]){
                if(nums[L]<=target&&target<nums[M]){
                    R=M-1;
                }else{
                    L=M+1;
                }
            }else{
                if(nums[M]<target&&target<=nums[R]){
                    L=M+1;
                }else{
                    R=M-1;
                }
            }
        }
        return false;
    }
}
